import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Solution {

    public static void main(String[] args) {
        Solution test = new Solution();
        // int[] arr = new int[]{1,2,3,4};
        // System.out.println(test.longestSubsequence(arr, 2));

        int[] arr = new int[]{1,2,3,4,5,6,7,8};
        System.out.println(test.lenLongestFibSubseq(arr));
    }

    public int longestSubsequence(int[] arr, int diff) {
        /**
         * 最长等差子序列
         * 状态表示：
         *  dp[i]表示以i下标为结尾的所有子序列中，最长定差子序列的长度
         * 状态转移方程：
         *  if(arr[i] - arr[j] == diff) {
         *      dp[i] = dp[j] + 1;
         *      break;
         *  }
         * 初始化：
         *  由于每一个元素都可以视作一个定差子序列，因此dp表最长情况为1
         *  故使用1初始化dp表所有元素
         * 返回值：
         *  返回dp表中最大值
         * 提交代码出现的问题：
         *  1，代码逻辑没有问题，但是时间复杂度超出限制，需要对代码进行优化
         * 优化思路：
         *  由于是定差子序列，故当我们以i下标元素为结尾时，前一个元素其实已经确定了
         *  故我们可以使用Map进行存储数据，若是前一个值存在于Map中，则加上这个值；若是不存在，直接跳过，省去一层循环
         *  并且若是存在相同的值，那么后面值长度必定大于前面值的长度，因此是定差的，所以不用担心去重
         * */
        // 1 初始化
        int n = arr.length;
        // 2 创建dp表
        int[] dp = new int[n];
        Map<Integer, Integer> map = new HashMap<>();
        // 3 初始化
        Arrays.fill(dp ,1);
        // 4 填表
        int maxLength = 1;
        for(int i = 0; i < n; i++) {
            int target = arr[i] - diff;
            if(map.containsKey(target)) {
                // -前一个值存在

                // 当前值 = 前一个值长度 + 1
                dp[i] = map.get(target) + 1;
                // 将当前值存储至dp表中
                map.put(arr[i], dp[i]);
                maxLength = Math.max(dp[i], maxLength);
            } else {
                // -前一个值不存在
                map.put(arr[i], 1);
            }
        }
        // 5 返回值
        return maxLength;
    }

    public int lenLongestFibSubseq(int[] arr) {
        /**
         * 最长斐波那契子序列长度
         * 状态表示：
         *  我们若想由i得知前一个元素的值，按照题干所说，则必须使用两个值进行表示
         *  dp[i][j]表示以i下标元素与j下标元素为结尾的所有子序列中，最长斐波那契子序列长度，并规定 i>j
         * 状态转移方程：
         *  if(arr[j] - arr[i] 存在) {
         *      dp[i][j] = dp[k][i] + 1;
         *  }
         * 初始化：
         *  暂时感觉不用初始化
         * 返回值：
         *  返回dp表中的最大值
         * */
        // 1 初始化
        int n = arr.length;
        // 2 创建dp表
        int[][] dp = new int[n][n];
        Map<Integer, Integer> map = new HashMap<>();
        // 3 初始化
        map.put(arr[0], 0);
        // -由状表可得，其已经有两个元素了，故最短为2
        for(int i = 0; i < n; i ++) {
            for(int j = 0; j < n; j++) {
                dp[i][j] = 2;
            }
        }
        // 4 填表
        int maxLength = 0;
        for(int i = 1; i < n-1; i++) {
            for(int j = i+1; j < n; j++) {
                int target = arr[j] - arr[i];
                // -若存在
                if(map.containsKey(target)) {
                    dp[i][j] = dp[map.get(target)][i] + 1;
                    maxLength = Math.max(dp[i][j], maxLength);
                }
            }
            // -将最新数组元素及其下标存储至map中
            map.put(arr[i], i);
        }
        // 5 返回值
        return maxLength;
    }
}
